Constructing spatial discretizations for sparse multivariate trigonometric polynomials that allow for a fast discrete Fourier transform

摘要

The paper discusses the construction of high dimensional spatialdiscretizations for arbitrary multivariate trigonometric polynomials, where thefrequency support of the trigonometric polynomial is known. We suggest aconstruction based on the union of several rank-1 lattices as sampling schemeand call such schemes multiple rank-1 lattices. This approach automaticallymakes available a fast discrete Fourier transform (FFT) on the data. The key objective of the construction of spatial discretizations is theunique reconstruction of the trigonometric polynomial using the sampling valuesat the sampling nodes. We develop construction methods for multiple rank-1lattices that allow for this unique reconstruction and for estimates of thenumber $M$ of distinct sampling nodes within the resulting spatialdiscretizations. Assuming that the multivariate trigonometric polynomial underconsideration is a linear combination of $T$ trigonometric monomials, theoversampling factor $M/T$ is independent of the spatial dimension and, roughlyspeaking, with high probability only logarithmic in $T$, which is much betterthan the oversampling factor that is expected when using one single rank-1lattice. The newly developed approaches for the construction of spatialdiscretizations are probabilistic methods. The arithmetic complexity of thesealgorithms depend only linearly on the spatial dimension and, with highprobability, only linearly on $T$ up to some logarithmic factors. Furthermore, we analyze the computational complexities of the resulting FFTalgorithms in detail and obtain upper bounds in $\mathcal{O}\left(M\logM\right)$, where the constants depend only linearly on the spatial dimension.With high probability, we construct spatial discretizations where $M/T\le C\logT$ holds, which implies that the complexity of the corresponding FFT convertsto $\mathcal{O}\left(T\log^2 T\right)$.